This section is intended to introduce various aspects of the art, which may be associated with aspects of the disclosed techniques and methodologies. A list of references is provided at the end of this section and may be referred to hereinafter. This discussion, including the references, is believed to assist in providing a framework to facilitate a better understanding of particular aspects of the disclosure. Accordingly, this section should be read in this light and not necessarily as admissions of prior art.
Nonlinear optimization problems may arise in many disciplines such as finance, manufacturing, transportation, or the exploration and production of hydrocarbon resources. A basic optimization method for minimizing a particular quantity predicted by a numerical model can be formulated as depicted in FIG. 1, in which the method is indicated at 10. At block 12 a set of model parameter values are chosen. At block 13 the parameter values are run through a numerical model to predict the quantity. At block 14 it is determined whether the quantity is sufficiently minimized or if a prescribed number of iterations is exceeded. If so, the method ends at block 15. Otherwise, new parameter values are chosen at block 12 and the method repeats.
Another optimization method is to compare the outputs of a numerical model with some data or observations. The objective is to find a set of model parameters which maximize the likeness, or minimize the difference, between predictions and observations. This difference is termed the misfit, cost, or cost function. Evaluating the cost function for all possible combinations of parameters defines a response surface. This method, known as inversion, can be considered as finding the response-surface minimum or minima. Applications of inversion in the field of hydrocarbon exploration and production include seismic inversion, geologic modeling, and history matching. FIG. 2 is a flowchart showing a simple known inversion method, indicated generally at 20. At block 22 a set of model parameter values are chosen. At block 23 the parameter values are run through a numerical model to provide a prediction of the output, shown at block 24. The prediction is compared with observed characteristics or data, shown at block 25, to create a cost function. At block 26 it is determined whether the cost function is sufficiently minimized. If so, the method ends at block 27. If not, new parameter values are chosen at block 22 and the method repeats.
Because a complex problem such as geologic modeling may have many independent or free parameters, constructing a response surface for a geologic model by evaluating all possible combinations of parameters is rarely possible. Even constructing an approximate response surface by systematic sampling of the parameter space (and thus systematic testing of parameters) typically is prohibitive for more than just a few free parameters sought by the inversion.
Instead, iterative sampling of the parameter space is often performed, and the issue is to select parameter values to be used in the iterative process. One strategy is to find the points in the parameter space where the gradient of the cost function vanishes, or in other words, the points where the response surface is flat. These points show locally maximal or minimal values for the cost function and have either locally maximal or minimal likeness with the observations. At all other points, the gradients are nonzero and denote the direction in which values of the cost function reduce the most, thus indicating the direction towards parameters with lower costs. As shown in the method 30 of FIG. 3, at block 32 an initial set of parameters is chosen, which is equivalent to choosing an initial point on the response surface. At block 34 the numerical model can be used to evaluate the cost function and its gradient. At block 36 new parameter values in the parameter space downhill on the response surface from previous values are chosen when the cost function is not sufficiently minimized. This method can be repeated until a minimum is reached or until the number of iterations exceeds a prescribed limit. Unfortunately for many problems, there exist various minima on the response surface which nearly guarantee that the found solution is not the global optimum but just a local one. In other words, the solution gets trapped in a local minimum.
Another strategy of parameter selection is sampling the response surface and building a response-surface model which guides the parameter selection. This is shown in the method 40 depicted in FIG. 4, in which at block 42 a response-surface model is estimated based on the outputs of the numerical model and the associated cost function. With each iteration, the response-surface model is updated, hopefully leading to a better selection of parameters (at block 44) to be used in the next iteration. Response-surface model methods often recombine the parameters of the currently best solutions or generate new parameters near the currently best ones. In practice, some degree of randomness may be introduced to keep scouting for promising areas of the response surface to reduce the risk of getting stuck in local minima.
Many attempts have been made to solve various problems associated with optimization methods and algorithms. For example, Sambridge (1999) presents a global optimization method which dynamically partitions the parameter space by Voronoi tessellation. However, only the evaluation of the cost function is considered, and there is no proposal to complement the cost function with the cost function gradient. Thus, the response surface is modeled to be piecewise constant.
Rickwood and Sambridge (2006) reveal a modification to the original neighborhood algorithm which is better suited for parallel computing environments. The original algorithm evaluated the parameters and updated the response surface model in batches which synchronized the algorithm and forced periodic pauses to allow all the processors to catch up. The modification removes this barrier, but does not reveal usage of cost function gradients.
U.S. Pat. No. 4,935,877 to Koza presents a non-linear genetic algorithm for solving optimization problems but does not address inclusion of cost function gradient information.
U.S. Pat. No. 7,216,004 B2 to Kohn et al., U.S. Pat. No. 7,072,723 B2 to Kohn et al., and U.S. Patent Publication No. US2005/0102044 to Kohn et al. reveal methods and systems for finding optimal or near optimal solutions for generic optimization problems by an approach to minimizing functions over high-dimensional domains that mathematically model the optimization problems. These methods transform the cost function into systems of differential equations which are solved numerically. What is not disclosed is usage of a response surface model or a discrete approximation of the cost function.
U.S. Patent Publication No. US20030220772 A1 to Chiang et al. discloses an optimization method which finds a plurality of local optima, and then selects the best among them.
Teughels et al. (2003) presents an optimization method which combines global with local optimization but does not reveal the usage of Voronoi or Delaunay tessellation for building a response surface model.
Shang and Wah (1996) present a hybrid optimization method that combines global and local searches to explore the solution space, locate promising regions, and find local minima. To guide exploration of the solution space, it uses the gradients to explore local minima, but pulls out once little improvement is found. The algorithm is based on neural network methodology and does not use an explicit discretization of a cost function.
The foregoing discussion of need in the art is intended to be representative rather than exhaustive. A technology addressing one or more such needs, or some other related shortcoming in the field, would benefit drilling and reservoir development planning, for example, providing decisions or plans for developing a reservoir more effectively and more profitably.
Reference material which may be relevant to the invention, and which may be referred to herein, include the following:
Sambridge, “Geophysical Inversion with a Neighbourhood Algorithm -I. Searching a parameter space,” Geophysical Journal International, 138, 479-494, 1999.
Rickwood and Sambridge, “Efficient parallel inversion using the Neighbourhood Algorithm”, Geochemistry Geophysics Geosystems, 7, Q11001, doi: 10.1029/2006GC001246, 2006.
Shang and Wah, “Global Optimization for Neural Network Training,” IEEE Computer, 29(3), 45-54, 1996.
Teughels et al., “Global optimization by coupled local minimizers and its application to FE model updating,” Computers & Structures, 81(24-25), 2337-2351, 2003.
U.S. Pat. No. 4,935,877 to Koza, “Non-linear genetic algorithms for solving problems.”
U.S. Pat. No. 7,216,004 B2 to Kohn et al., “Method and system for optimization of general problems.”
U.S. Pat. No. 7,072,723 B2 to Kohn et al., “Method and system for optimization of general problems.”
U.S. Patent Publication No. US2005/0102044 A1 to Kohn et al., “Method and system for optimization of general symbolically expressed problems, for continuous repair of state functions, including state functions derived from solutions to computational optimization, for generalized control of computational processes, and for hierarchical meta-control and construction of computational processes.”
U.S. Patent Publication No. US20030220772 A1 to Chiang et al., “Dynamical methods for solving large-scale discrete and continuous optimization problems.”